# codding = utf-8
"""
# 妖怪和和尚过河问题
# 三个和尚and三个妖怪在河的左岸,他们都要过河，现在有一条限乘2只的船,爱坐不坐。
# 在任何时候,如果一边的和尚比妖怪少,妖怪就要把和尚吃掉
# 问：怎样过河,和尚不会被吃掉
"""

import os
import logging

logpath = 'debug.log'
if logpath is not None and logpath != '':
    if not os.path.exists(logpath):
        with open(logpath, "w") as f:
            f.close()
    logging.basicConfig(level=logging.DEBUG,
                        format='%(asctime)s %(filename)s[line:%(lineno)d] %(levelname)s %(message)s',
                        datefmt='%a, %d %b %Y %H:%M:%S',
                        filename=logpath,
                        filemode='w')

LEFT = -1
RIGHT = 1
"""
用五元组表示某个时刻的和尚、妖怪和船的状态
(left_monk,left_monster,right_monk,right_monster,boat_position:LEFT or RIGHT)
用类似状态的五元组构建动作的模型：
(left_monk_change , left_monster_change , right_monk_change , right_monster_change , boat_position:LEFT or RIGHT)
"""
actions = [
    (-2, 0, 2, 0, LEFT),
    (-1, 0, 2, 0, LEFT),
    (0, -2, 0, 2, LEFT),
    (0, -1, 0, 1, LEFT),
    (-1, -1, 1, 1, LEFT),
    (2, 0, -2, 0, RIGHT),
    (1, 0, -1, 0, RIGHT),
    (0, 2, 0, -2, RIGHT),
    (0, 1, 0, -1, RIGHT),
    (1, 1, -1, -1, RIGHT)
]


# 执行船运行为，返回运输后的状态
def act(t1: tuple, t2: tuple):
    return t1[0] + t2[0], t1[1] + t2[1], t1[2] + t2[2], t1[3] + t2[3], int(0 - (t1[4] + t2[4]) / 2)


# 判断船运方法合理性，对遍历条件进行修剪
def shipping(state: tuple, shipmethod: tuple):
    logging.debug('before ship:%s' % str(state))
    logging.debug('ship method:%s' % str(shipmethod))
    if state[-1] != shipmethod[-1]:
        logging.error('illegal position and method')
    else:
        tmpstate = act(state, shipmethod)
        if isshipleagal(tmpstate):
            state = tmpstate
        else:
            logging.error('>>>>>>  illegal shipmethod')
            pass
    logging.debug('after ship:%s' % str(state))
    return state


def isshipleagal(tmpstate: tuple):
    if tmpstate[0] > 3 or tmpstate[0] < 0 or tmpstate[1] < 0 or tmpstate[1] > 3 or tmpstate[2] > 3 or tmpstate[
        2] < 0 or tmpstate[3] < 0 or tmpstate[3] > 3 or (tmpstate[0] != 0 and tmpstate[0] < tmpstate[1]) or (
                    tmpstate[2] != 0 and tmpstate[2] < tmpstate[3]) or abs(tmpstate[4]) != 1:
        return False
    return True


def acrossriver(state, visithistory=None):
    logging.debug('state=%s ' % str(state))
    if visithistory is None:
        visithistory = []
    if state in visithistory:
        logging.debug('visited state')
        return
    visithistory.append(state)
    tmpvisithistory = visithistory.copy()
    logging.debug('history:' + str(visithistory))
    if state == (0, 0, 3, 3, 1):
        print(visithistory)
        return
    for shipmethod in actions:
        tmpstate = shipping(state, shipmethod)
        # 如果action实施成功
        if tmpstate != state:
            acrossriver(tmpstate, visithistory)
        visithistory = tmpvisithistory.copy()


if __name__ == '__main__':
    initstate = (3, 3, 0, 0, LEFT)
    acrossriver(initstate)
